package main

import (
	"fmt"
	"math/rand"
	"time"
)

func main() {

	head := &ListNode{1, nil}
	head.next = &ListNode{2, nil}
	head.next.next = &ListNode{3, nil}
	res := Constructor(head)
	n := res.GetRandom()
	fmt.Println(n)

}

/*
给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。
进阶:
如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？
示例:
// 初始化一个单链表 [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);
// getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
solution.getRandom();
*/

//type Solution struct {
//	head *ListNode
//	size int
//	list []int
//}
//type ListNode struct {
//	Val int
//	Next *ListNode
//}
//
///** @param head The linked list's head.
//Note that the head is guaranteed to be not null, so it contains at least one node. */
//func Constructor(head *ListNode) Solution {
//	solution := Solution{}
//	if head == nil {
//		return solution
//	}
//	solution.size = 1
//	solution.list = append(solution.list, head.Val)
//	node := head.Next
//	for node != nil {
//		solution.list = append(solution.list, node.Val)
//		solution.size++
//		node = node.Next
//	}
//
//	return solution
//}
//
///** Returns a random node's value. */
//func (this *Solution) GetRandom() int {
//	index := rand.Intn(this.size)
//
//	return this.list[index]
//}
//
//func init()  {
//	rand.Seed(time.Now().Unix())
//}


